
/* domain
        Dom_Node = Node &        
        Dom_Empty = Empty
*/

sealed abstract class BST {
  def contains(key: Int): Boolean = (this : BST) match {
    case Node(left: Empty,value: Int, _) if key < value => left.contains(key)
    /** missing Node(Node,_,_) if key < value ...*/
    case Node(_,value: Int, right: BST) if key > value => right.contains(key)
    case Node(_,value: Int, _) if key == value => true
    case e : Empty => false 
  }
}
class Empty extends BST
class Node(val left: BST, val value: Int, val right: BST) extends BST


object Node {
    
  def apply(left: BST, value: Int, right: BST): Node = 
    new Node(left,value,right)
    
  def unapply(n: Node): Option[(BST,Int,BST)] =
    Some(Tuple3(n.left,n.value,n.right))
}

object Empty {
    
  def apply(): Empty = new Empty()
  
  def unapply(e: Empty): Boolean = true
}

object Main {

  def main(args: Array[String]): Unit =
    Node(Node(Empty(),3,Empty()),5,Empty()).contains(3)
}



